/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2022-11-04
 * Time: 8:32
 */
public class SingleLinkedList {
     static class ListNode{
          int val;
          ListNode next;
          ListNode(int val){
               this.val = val;
          }
     }
     ListNode head;
     public void addFirst(int data){
          ListNode node = new ListNode(data);
          if(head == null){
               head = node;
               return;
          }
          node.next = head;
          head = node;
     }
//     //尾插法
     public void addLast(int data){
          ListNode node =new ListNode(data);
          if(head ==null){
               head =node;
               return;
          }
          ListNode cur = head;
          while (cur.next != null){
               cur = cur.next;
          }
          cur.next = node;
     }

     //任意位置插入,第一个数据节点为0号下标
     public void addIndex(int index,int data){
          if(index <0 || index >size()){
               throw new Indexwrongful("index位置不合法");
          }
          if(index == 0){
               addFirst(data);
               return;
          }
          if(index == size()){
               addLast(data);
               return;
          }
          ListNode cur = findindex(index);
          ListNode node = new ListNode(data);
          node.next = cur.next;
          cur.next = node;
     }

     private ListNode findindex(int index) {
          ListNode cur = head;
          int count = index-1;
          while (count !=0){
               cur= cur.next;
               count--;
          }
          return cur;
     }

          //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
          ListNode cur = head;
          while (cur != null){
               if(cur.val == key){
                    return true;
               }
               cur =cur.next;
          }
          return false;
     }
     //删除第一次出现关键字为key的节点
     public void remove(int key){
          if(head == null){
               return;
          }
          if(head.val == key){
               head = head.next;
               return;
          }
          ListNode cur = findkey(key);
          if(cur ==null){
               System.out.println("不存在");
               return;
          }
          cur.next = cur.next.next;
     }

     private ListNode findkey(int key) {
          ListNode cur = head;
          while (cur.next!= null){
               if(cur.next.val ==key){
                    return cur;
               }
               cur =cur.next;
          }
          return null;
     }

     //     //删除所有值为key的节点
     public void removeAllKey(int key){
          if(head == null){
               return;
          }
          ListNode cur = head.next;
          ListNode pre = head;
          while (cur != null) {
               if (cur.val == key) {
                    pre.next = cur.next;
                    cur = cur.next;
               } else {
                    pre = cur;
                    cur = cur.next;
               }
          }
          if(head.val == key){
               head = head.next;
          }
     }
//     //得到单链表的长度
     public int size(){
          int count = 0;
          ListNode cur = head;
          while (cur != null){
               cur= cur.next;
               count++;
          }
          return count;
     }

     public void display(){
          ListNode cur = head;
          while (cur != null){
               System.out.print(cur.val+" ");
               cur = cur.next;
          }
     }

//     public void clear();
}
